package labuladong;

/**
 * 给定不同面额的硬币coins和一个个总金额amount，写一个函数来计算可以凑成总金额的硬币组合数，假设每一种面额的硬币有无限个
 */

public class _完全背包 {
    public static void main(String[] args) {
        // 答案4: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
        // 总金额
        int amount = 5;
        // 不同面额的硬币数
        int[] coins = {1, 2, 5};
        int target = change(amount, coins);
        System.out.println(target);
    }

    public static int change(int amount, int[] coins) {
        // dp[i][j]表示若只使用前i个物品，当背包容量为i时，有dp[i][j]种方法可以装满背包
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        // 初始化
        // 若凑出的背包容量为0，无为而治就是唯一的一种凑法
        for (int i = 1 ; i <= n ; i++) {
            dp[i][0] = 1;
        }
        // 若不使用任何物品，就无法凑出任意金额
        for (int i = 1 ; i <= amount ; i++) {
            dp[0][i] = 0;
        }
        for (int i = 1 ; i <= n ; i++) {
            for (int j = 1 ; j <= amount ; j++) {
                if (j - coins[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][amount];
    }
}
